package leetcode_jz_offer.day14_sousuoAndHuisu;

/**
 * 给定一个mxn二维字符网格board和一个字符串单词word
 * 如果word存在于网格中，返回true；否则返回 false。
 *
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，
 * 其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用
 *
 **/

/**
 * 思路：board遍历找到与word的第一个字符相同的位开始遍历
 * 开始递归找路径：当word走完时说明有这个路径->true
 * 创建judge数组判断是否已经使用过（回溯必要的判断容器）
 * 当下标i,j不满足条件,或者board[i][j]的值与word.charAt(index)的值不同或者已经使用过当前位置时，直接返回false
 * 递归判断上下左右格子的字符是否符合条件
 *
 */
public class Num12_矩阵中的路径 {
    boolean[][] judge;//用于判断是否当前格子已经走过
    public boolean exist(char[][] board, String word) {
        int m=board.length;
        int n=board[0].length;
        judge = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                //寻找与目标值第一个字母相同再进行判断 相当于找起点 节省时间
                if(board[i][j]==word.charAt(0)){
                    if(check(board,word,0,i,j)){
                        return true;
                    }
                }
            }
        }
        return false;
    }
    //检查路径是否存在
    private boolean check(char[][] board, String word, int index, int i, int j) {
        //当前索引已经走完word 相当于找到路径
        if(index==word.length()){
            return true;
        }
        //不符合要求的参数直接返回
        if(i<0||i>=board.length||j<0||j>=board[0].length||board[i][j]!=word.charAt(index)||judge[i][j]){
            return false;
        }
        //当前点可用 进行标记 防止反复使用
        judge[i][j]=true;
        //上下左右四方向有一个能走通则存在
        if(check(board,word,index+1,i+1,j)||check(board,word,index+1,i-1,j)||check(board,word,index+1,i,j+1)||check(board,word,index+1,i,j-1)){
            return true;
        }
        //取消标记
        judge[i][j]=false;
        return false;
    }


}
